#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 5 + 100;
const int maxn = 5 + 1e7;

const int mod = 998244353;
int f[max_size];
ll pre[max_size];
int fsiz;
inline void init_fi() {
    f[++fsiz] = 1, pre[fsiz] = 1;
    while (f[fsiz] < maxn) {
        ++fsiz, f[fsiz] = f[fsiz - 1] + f[fsiz - 2];
        pre[fsiz] = pre[fsiz - 1] + f[fsiz];
    }
}

int dp[maxn];

int main() {
    init_fi();
    dp[0] = 1, dp[1] = 1;
    for (int i = 2; i <= fsiz; ++i) {
        for (int j = min(3 * f[i], maxn - 1); j >= f[i]; --j) {
            dp[j] = (dp[j] + (ll)f[i] * dp[j - f[i]]) % mod;
        }
    }
    int Q = rad();
    while (Q--) {
        int x = rad();
        printf("%d\n", dp[x]);
    }
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}
/*
100
1
2
3
4
5
6
7
*/